/*
 * @lc app=leetcode.cn id=851 lang=typescript
 *
 * [851] 喧闹和富有
 */

// @lc code=start
function loudAndRich(richer: number[][], quiet: number[]): number[] {
  const n = quiet.length;
  const graph = new Array(n).fill(0).map(() => []);
  // 建图，每个人的邻居
  for (const [a, b] of richer) {
    graph[b].push(a);
  }
  // 深度优先搜索，将quiet值最小的邻居找出来
  const dfs = (x: number, ans: number[]): void => {
    if (ans[x] !== -1) return;
    ans[x] = x;
    for (const y of graph[x]) {
      dfs(y, ans);
      if (quiet[ans[y]] < quiet[ans[x]]) {
        ans[x] = ans[y];
      }
    }
  };

  const ans: number[] = new Array(n).fill(-1);
  for (let i = 0; i < n; i++) {
    dfs(i, ans);
  }

  return ans;
}
// @lc code=end
